{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Longest Palindromic Substring\n",
    "\n",
    "[The Original Question](https://mp.weixin.qq.com/s/LP6Q8LD1R4WMHqXxZSwABg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question\n",
    "\n",
    "A palindrome is a sequence of characters that reads the same backwards and forwards.\n",
    "\n",
    "Given a string, s, find the longest palindromic substring in s."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "```\n",
    "Input: \"banana\"\n",
    "Output: \"anana\"\n",
    "\n",
    "Input: \"million\"\n",
    "Output: \"illi\"\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "anana\n",
      "illi\n"
     ]
    }
   ],
   "source": [
    "def longestPal(string: str) -> str:\n",
    "    \n",
    "    # The whole string is a palindrome.\n",
    "    if (len(string) < 2) or (string == string[::-1]):\n",
    "        return string\n",
    "    \n",
    "    n = len(string)\n",
    "    \n",
    "    # Define the start index and max length of palindrome.\n",
    "    (start, maxlen) = (0, 1)\n",
    "    \n",
    "    # Start from 1 directly,\n",
    "    # because (i = 0) have no posibilities larger than maxlen. \n",
    "    for i in range(1, n):\n",
    "        \n",
    "        # Slice i and (maxlen + 2) characters before i.\n",
    "        # len(odd) = maxlen + 2\n",
    "        odd = string[i - maxlen - 1:i + 1]\n",
    "        \n",
    "        # Slice i and (maxlen + 1) characters before i.\n",
    "        # len(even) = maxlen + 1\n",
    "        even = string[i - maxlen:i + 1]\n",
    "        \n",
    "        # Check if there exists a palindromic string.\n",
    "        if i - maxlen - 1 >= 0 and odd == odd[::-1]:\n",
    "            start = i - maxlen - 1\n",
    "            maxlen += 2\n",
    "            continue\n",
    "            pass\n",
    "        if i - maxlen >= 0 and even == even[::-1]:\n",
    "            start = i - maxlen\n",
    "            maxlen += 1\n",
    "            pass\n",
    "        pass\n",
    "    return string[start:start + maxlen]\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(longestPal('banana'))\n",
    "    print(longestPal('million'))\n",
    "    pass"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
